1. Field of the Invention
The invention relates generally to the processing of streams of digital data in devices such as packet switches and routers and more specifically to processing such as multicasting packets to a number of streams, discarding packets in a stream, and scheduling, including shaping output streams and segmenting or reassembling them.
2. Description of Related Art: FIG. 1
Packets and Protocols
Communication among digital systems is generally by means of packets. A packet is shown at 113 in FIG. 1. A packet is simply a sequence of bits whose meaning is determined by a protocol. The protocol defines how the digital devices which-process the packet are to interpret the bits in the packet. Regardless of protocol, most packets have a header 115, which indicates how that particular packet is to be processed according to the protocol, and a payload 117, which is the actual information being communicated by the packet. A packet may also have a trailer 119, which may simply indicate the end of the packet, but may also contain information which permits detection and/or correction of errors that have occurred during transmission or processing of the packet. Depending on the protocol which defines it, a packet may have a fixed length or a varying length. In the following discussion, the contents of the header 115 and trailer 119 will be termed protocol data, since the manner in which these contents are interpreted is determined completely by the protocol, and the contents of payload 117 will be termed payload data. Packets for certain protocols are often termed frames or cells.
Packets are used for communication in digital systems at many different levels. Thus, the payload of a group of packets at one level of the digital system may be a packet at a higher level. That is shown at 137 in FIG. 1. IP packet 121 is a packet which is interpreted according to the IP protocol. IP packets 121 have an IP header 123 and a varying-length IP payload 125. Included in the information in IP header 123 is the length of IP payload 125. When IP packet 121 is transported across a physical network, it is carried in the payload of a stream 135 of transport packets 127. Each transport packet 127 has its own header 129, payload 131, and trailer 133. What are termed transport packets herein are packets at the link layer of the ISO seven-layer model. Transport packets may have fixed or varying lengths, depending on the protocol used in the link layer.
The devices that deal with the transport packets do so as indicated by header 129 and trailer 133 in the packets, and do not examine the contents of payload 131. When a transport packet reaches its destination, the payload is passed to the part of the system for which it is intended, in this case, a component which operates according to the IP protocol, and this component deals with IP packet 121 as indicated in IP header 123. Of course, IP payload 125 may be a packet for another, still higher level. For example, it may be a packet destined for a decrypter, and the payload of that packet may be an encrypted IP packet 121. In such a case, the component that deals with IP packet 121 passes the payload to the decrypter, which decrypts the encrypted IP packet 121 and returns the decrypted IP packet to the component that deals with IP packets for further processing. That processing may of course include sending the decrypted IP packet to another destination, and if communication with that destination is via the protocol for transport packets 127, the component that deals with IP packets will provide the decrypted IP packet to the component that produces transport packet streams and the decrypted IP packet will be carried in the payload of the transport packets 127.
Packet Switches
When packets are used to communicate between digital systems that are located remotely from each other, the packets move on digital networks that connect the systems. At the physical level, the digital network may employ any medium to transmit a signal between two devices, for example, the ether, a conducting wire, or an optical cable. Packets are routed among transmission paths by packet switches. The packet switch routes the packet according to information that is typically contained in the packet header.
As one would expect, each kind of protocol has its own routing rules. For example, the IP protocol uses logical routing; each source or destination of an IP packet has a logical IP address, and an IP packet intended for a given destination has that destination's logical IP address in its header. The header does not indicate the physical location of the destination. The IP packet switch must translate the IP address into a physical address that will get the packet at least part of the way to its destination and must also make a stream 135 of transport packets directed to that physical address that carry the IP packet as their payload 131. Thus, IP node 109(n) is on Ethernet node 107(n) on Ethernet LAN 105(a) and an IP packet switch that is connected to LAN 105(a) must respond to an IP packet addressed to IP node 109(n) by making a stream of Ethernet packets directed to Ethernet node 107(n) that carry the IP packet as their payload.
A typical packet switch is shown at 103. Packet switch 103 is connected to a number of physical media 106, by means of which packet switch 103 may receive and transmit data. Examples of such media may be fiber optic cables or cables made up of electrical conductors. Each such medium 106 has its own protocol for defining the data sent via the medium; for example, one widely-used protocol for sending data via an optical cable is the SONET protocol. In FIG. 1, media 106(a . . . m) are optical cables using the SONET protocol, while media 106(n . . . z) are electrical cables. Packets at the level of the medium, termed herein medium packets, have as their payload transport packets. In terms of the ISO 7-layer model, the medium packets are physical-layer packets. In switch 103, the transport packets that are sent and received on the optical cables are packets made according to the ATM protocol used in ATM wide-area network 111, while the transport packets that are sent and received on the electrical cables are made according to the Ethernet™ protocol used in local area networks 109. In many cases, the transport packets have IP packets as their payloads, and in those cases, packet switch 103 routes the IP packets to IP nodes 109. As described above, it does so by determining the medium 106(i) upon which the IP packet should move to reach its destination and then making a stream of packets according to the protocol required for the medium that have the transport packet stream used with that medium as their payloads, and these in turn have the IP packet as their payload. Thus, if packet switch 103 receives an IP packet from WAN 111 that is directed to IP node 109(n) and IP node 109(n) is in Ethernet node 107(n) on Ethernet LAN 105(a), packet switch 103 must make a stream of packets in the form required by medium 106(n) whose payload is a stream of Ethernet packets directed to Ethernet node 107(n) that in turn carry the IP packet as their payload.
The functions performed by a packet switch 103 depend on the network environment in which the packet switch is operating and the capabilities of the packet switch. The functions that are important for the following discussion will be termed herein traffic management functions. There are three general groups of traffic management functions:
routing packets received from a particular source to one or more different destinations.
transforming packet streams as required for the routing.
controlling traffic, so that neither switch 103 nor the devices it transmits data to is overwhelmed and so that switch 103 and the networks it serves are fairly and efficiently utilized.
Continuing with these functions in more detail, routing includes filtering and multicasting. Filtering is performed at network boundaries. Packet switch 103 is shown here as being at the boundary between a private network 104 and a public network 102. The header of each IP packet 121 contains the source IP address and destination IP address for the packet, and the security policies of private network 104 bar access by IP packets from public network 102 with certain source addresses to private network 104 and also bar access by packets from private network 104 with certain source addresses to public network 102. Switch 103 filters each incoming IP packet by comparing its source address with a list of source addresses which are to be barred, and if the incoming packet is on the list, it is discarded. Switch 103 filters outgoing packets in a similar fashion. Multicasting is sending copies of a packet received from a source to multiple destinations.
Stream transformation includes operations such as the one described above of transforming an IP packet that is received as a stream of ATM transport packets into an IP packet that is output to it its destination as a stream of Ethernet transport packets. Such operations typically involve reassembling the higher-level packet from the payloads of its transport packets when the higher-level packet is received in the switch and segmenting the higher-level packet into transport packets when it is transmitted from the switch. Stream translation also includes encryption and decryption of payloads. One place where encryption or decryption occurs is at network boundaries. For example, a security policy of private network 104 may require that IP packets sent to certain destinations in public network 102 be encrypted, and the encryption may be done in switch 103. Switch 103 may also decrypt packets coming from those destinations when they enter private network 104.
Controlling traffic includes protecting switch 103 and destinations downstream of it from being overloaded by discarding packets and scheduling output of packets from switch 103 so that output bandwidth is efficiently used and so that to the extent possible, the requirements of each output stream with regard to network resources and timing can be satisfied. The requirements of an output steam in this regard are called its service class. The packet switch must be able to handle service classes ranging from e-mail where all that is required is that the e-mail arrive at a reasonable time (measured in hours) after it has been posted through digital TV, in which the packets must arrive at their destination within fixed time intervals of each other, to packet telephony, where there are strict constraints not only on the time intervals between packets, but also on the total length of time it takes a packet to traverse the network from its source to its destination.
Reference numbers in the drawing have three or more digits: generally, the two right-hand digits are reference numbers in the drawing indicated by the remaining digits. Thus, an item with the reference number 203 first appears as item 203 in FIG. 2. Exceptions to this rule are indicated in the following table:
Reference NumbersFigures 6xx6, 31 7xx 7, 32, 33 8xx8, 34 9xx9, 3520xx20, 38, 3923xx23, 36 24xx24, 37 30xx30, 40, 41